/*
 * seq_list.c
 *
 *  Created on: 2020��9��18��
 *      Author: Administrator
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "../../include/list/seq_list.h"

bool init_seq_list(SeqList* list) {

	if (list == NULL) return false;
	list->last = -1;
	return true;
}

bool create_seq_list(SeqList* list, ElemType array[], int length) {

	if (list->last != -1) {
		return false;
	} else {
		for (int i = 0; i < length; i++) {
			list->last++;
			list->elem[list->last] = array[list->last];
		}
		return true;
	}
}

bool is_empty_seq_list(SeqList* list) {

	if (list->last == -1) return true;
	return false;
}

bool is_full_seq_list(SeqList* list) {

	if (list->last == MAXSIZE - 1) return true;
	return false;
}

int search_seq_list(SeqList* list, ElemType key) {

	int i = 0;
	while (i <= list->last) {
		if (list->elem[i] == key) {
			return i;
		}
		i++;
	}
	return -1;
}

int bin_search_seq_list(SeqList* list, ElemType key) {

	int low = 0;
	int high = list->last;
	int mid;

	while (low <= high) {
		mid = (low + high) / 2;
		if (list->elem[mid] == key) {
			return mid;
		} else if (list->elem[mid] > key) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return -1;
}

int rbin_search_seq_list(SeqList* list, ElemType key, int low, int high) {

	if (low > high) return -1;
	else {
		int mid = (low + high) / 2;
		if (list->elem[mid] == key)
			return mid;
		else if (list->elem[mid] > key)
			return rbin_search_seq_list(list, key, low, mid-1);
		else
			return rbin_search_seq_list(list, key, mid+1, high);
	}
}

bool insert_seq_list(SeqList* list, int i, ElemType e) {

	/*�����жϲ���λ���Ƿ�Ϸ�*/
	if ((i < 1) || (i > list->last + 2)) {
		printf("����λ��iֵ���Ϸ�");
		return false;
	}
	if (list->last >= MAXSIZE - 1) {
		printf("�������޷�����");
		return false;
	}
	/*Ϊ����Ԫ�ض��ƶ�λ��*/
	for (int k = list->last; k >= i-1; k--)
		list->elem[k + 1] = list->elem[k];
	list->elem[i-1] = e;
	list->last++;
	return true;
}

bool insert_tail_seq_list(SeqList* list, ElemType e) {

	if (is_full_seq_list(list)) return false;

	list->last++;
	list->elem[list->last] = e;
	return true;
}

ElemType delete_seq_list(SeqList* list, int i) {

	if ((i < 1) || (i > list->last + 1)) {
		printf("ɾ��λ�ò��Ϸ�!");
		return -1;
	}
	ElemType e = list->elem[i - 1]; /* ��ɾ����Ԫ�ش�ŵ�e��ָ��ı�����*/
	for (int k = i; k <= list->last; k++)
		list->elem[k-1] = list->elem[k]; /*�������Ԫ������ǰ��*/
	list->last--;
	return e;
}

SeqList* merge_seq_list(SeqList* listA, SeqList* listB) {

	int i=0, j=0, k=0;
	SeqList* listC = (SeqList* )malloc(sizeof(SeqList));

	while (i<=listA->last && j<=listB->last) {
		if (listA->elem[i] <= listB->elem[j]) {
			listC->elem[k] = listA->elem[i];
			i++;
			k++;
		} else {
			listC->elem[k] = listB->elem[j];
			j++;
			k++;
		}
	}
	/*����LA��ʣ��Ԫ��ʱ���򽫱�LA���µ�Ԫ�ظ�����LC*/
	while (i <= listA->last) {
		listC->elem[k] = listA->elem[i];
		i++;
		k++;
	}
	/*����LB��ʣ��Ԫ��ʱ���򽫱�LB���µ�Ԫ�ظ�����LC*/
	while (j <= listB->last) {
		listC->elem[k] = listB->elem[j];
		j++;
		k++;
	}
	listC->last = listA->last + listB->last + 1;
	return listC;
}

void print_seq_list(SeqList* list) {

	if (list->last == -1) {
		return;
	} else {
		for (int i = 0; i <= list->last; ++i) {
			printf("%d ", list->elem[i]);
		}
		printf("\n");
	}
}
